home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / stringsearch / bmsource / uf.rev.sdmd2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-06  |  2.9 KB  |  140 lines  |  [TEXT/MPS ]
  1. /*
  2.     search routine generated by gen.
  3.     skip=uf, match=rev (using revr), shift=sdmd2r
  4. */
  5. /*
  6.  * The authors of this software are Andrew Hume and Daniel Sunday.
  7.  * 
  8.  * Copyright (c) 1991 by AT&T and Daniel Sunday.
  9.  * 
  10.  * Permission to use, copy, modify, and distribute this software for any
  11.  * purpose without fee is hereby granted, provided that this entire notice
  12.  * is included in all copies of any software which is or includes a copy
  13.  * or modification of this software and in all copies of the supporting
  14.  * documentation for such software.
  15.  * 
  16.  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  17.  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
  18.  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  19.  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  20.  */
  21.  
  22. #ifndef    CHARTYPE
  23. #define    CHARTYPE    unsigned char
  24. #endif
  25. #define    MAXPAT    256
  26.  
  27. #include    "stats.h"
  28.  
  29. #ifndef    TABTYPE
  30. #define    TABTYPE    long
  31. #endif
  32. typedef TABTYPE Tab;
  33.  
  34. static struct
  35. {
  36.     int patlen;
  37.     CHARTYPE pat[MAXPAT];
  38.     Tab delta[256];
  39.     Tab sdelta1[256];
  40.     int md2;
  41. } pat;
  42.  
  43. prep(base, m)
  44.     CHARTYPE *base;
  45.     register m;
  46. {
  47.     CHARTYPE *skipc;
  48.     register CHARTYPE *pe, *p;
  49.     register int j;
  50.     register Tab *d;
  51.     register Tab *d1;
  52.     register j1, j2;
  53.     register CHARTYPE *pmd2;
  54.  
  55.     pat.patlen = m;
  56.     if(m > MAXPAT)
  57.         abort();
  58.     memcpy(pat.pat, base, m);
  59.     skipc = 0;
  60.     stats.len = m;
  61.     d = pat.delta;
  62.     for(j = 0; j < 256; j++)
  63.         d[j] = pat.patlen;
  64.     for(p = pat.pat, pe = p+m-1; p < pe; p++)
  65.         d[*p] = pe-p;
  66.     d[*p] = 0;
  67.     skipc = (CHARTYPE *)p;
  68.     d1 = pat.sdelta1;
  69.     for(pmd2 = skipc-1; pmd2 >= pat.pat; pmd2--)
  70.         if (*pmd2 == *skipc) break;
  71.     j2 = skipc - pmd2;    /* *pmd2 is first leftward reoccurance of *pe */
  72.     if(j2 < m+1)
  73.         j2 = m+1;
  74.     for(j1 = 0; j1 < 256; j1++)
  75.         d1[j1] = j2;
  76.     j2 = skipc - pmd2;    /* *pmd2 is first leftward reoccurance of *pe */
  77.     for(j1 = 0; j1 < m; j1++)
  78.         d1[base[j1]] = ((m-j1)<j2)? j2:(m-j1);
  79. #ifdef    STATS
  80.     stats.extra += pat.md2;
  81. #endif
  82. }
  83.  
  84. exec(base, n)
  85.     CHARTYPE *base;
  86. {
  87.     int nmatch = 0;
  88.     register CHARTYPE *e, *s;
  89.     register Tab *d0 = pat.delta;
  90.     register k;
  91.     register CHARTYPE *p, *q;
  92.     register CHARTYPE *prev = pat.pat+pat.patlen-1;
  93.     register Tab *d1 = pat.sdelta1;
  94.  
  95.     s = base+pat.patlen-1;
  96.     e = base+n;
  97.     memset(e, pat.pat[pat.patlen-1], pat.patlen);
  98.     while(s < e){
  99. #ifdef    STATS
  100.         k = d0[*s];
  101.         stats.jump++;
  102.         while(k){
  103.             stats.jump++; stats.step[k]++;
  104.             k = d0[*(s += k)];
  105.             stats.jump++; stats.step[k]++;
  106.             k = d0[*(s += k)];
  107.             stats.jump++; stats.step[k]++;
  108.             k = d0[*(s += k)];
  109.         }
  110. #else
  111.         k = d0[*s];
  112.         while(k){
  113.             k = d0[*(s += k)];
  114.             k = d0[*(s += k)];
  115.             k = d0[*(s += k)];
  116.         }
  117. #endif
  118.         if(s >= e)
  119.             break;
  120. #ifdef    STATS
  121.         stats.slow++;
  122. #endif
  123. #define    RH    s
  124.         for(p = prev, q = RH; p > pat.pat; ){
  125. #ifdef    STATS
  126.             stats.cmp++;
  127. #endif
  128.             if(*--q != *--p)
  129.                 goto mismatch;
  130.         }
  131.         nmatch++;
  132.     mismatch:
  133. #ifdef    STATS
  134.         stats.step[d1[s[1]]]++;
  135. #endif
  136.         s += d1[s[1]];
  137.     }
  138.     return(nmatch);
  139. }
  140.